`
https://leetcode.cn/problems/copy-list-with-random-pointer/
`

/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  // 两次遍历，第一次生成结点，第二次连接起来

  const toClone = new Map()

  for (let p = head; p !== null; p = p.next) {
    toClone.set(p, new _Node(p.val))
  }

  for (let p = head; p !== null; p = p.next) {
    if (p.next) toClone.get(p).next = toClone.get(p.next)
    if (p.random) toClone.get(p).random = toClone.get(p.random)
  }

  return toClone.get(head)
};